public class BianrySearchTree{
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val=val;
        }
    }
    public TreeNode root;
    //插入
    public void inset(int key){
        if(root==null){
            root=new TreeNode(key);
            return;
        }
        TreeNode parent=null;
        TreeNode cur=root;
        TreeNode node=new TreeNode(key);
        while(cur!=null){
            if(cur.val<key){
                parent=cur;
                cur=cur.right;
            }
            else if(cur.val>key){
                parent=cur;
                cur=cur.left;
            }
            else{
                return;
            }
        }
        if(parent.val>key) parent.left=node;
        else parent.right=node;
    }
    //查找
    public TreeNode search(int key){
        TreeNode cur=root;
        while(cur!=null){
            if(cur.val<key){
                cur=cur.right;
            }
            else if(cur.val==key){
                return cur;
            }else{
                cur=cur.left;
            }
        }
        return null;
    }
    //删除  
    public void Remove(int key){
        TreeNode cur=root;
        TreeNode parent=null;
        while(cur.val!=key){
            if(cur.val>key){
                parent=cur;
                cur=cur.left;
            }
            else if(cur.val<key){
                parent=cur;
                cur=cur.right;
            }
            else{
                return;
            }
        }
        //cur左边空
        if(cur.left==null){
            if(cur==root){
                root=cur.right;
            }
            else if(parent.left==cur){
                parent.left=cur.right;
            }
            else{
                parent.right=cur.right;
            }
        }
        else if(cur.right==null){
            if(cur==root){
                root=cur.left;
            }
            else if(parent.right==cur){
                parent.right=cur.left;
            }
            else{
                parent.left=cur.left;
            }
        }
        else{
            //cur左右不为空
            //替换删除->找cur右子树最小值或者左子树最大值替换cur
            //右子树替换
            TreeNode t=cur.right;
            TreeNode tp=cur;
            while(t.left!=null){
                    tp=t;
                    t=t.left;
            }
            cur.val=t.val;
            if(tp.left==t){
                tp.left=t.right;//null
            } //左子树没有左节点           
            else{
                tp.right=t.right;
            }
        }
        

    }
}